package com.sheng.leetcode.year2023.month02.day02;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2023/02/02
 * <p>
 * 1129. 颜色交替的最短路径<p>
 * <p>
 * 在一个有向图中，节点分别标记为 0, 1, ..., n-1。图中每条边为红色或者蓝色，且存在自环或平行边。<p>
 * red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。<p>
 * 类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。<p>
 * 返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边<p>
 * 交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []<p>
 * 输出：[0,1,-1]<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]<p>
 * 输出：[0,1,-1]<p>
 * <p>
 * 示例 3：<p>
 * 输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]<p>
 * 输出：[0,-1,-1]<p>
 * <p>
 * 示例 4：<p>
 * 输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]<p>
 * 输出：[0,1,2]<p>
 * <p>
 * 示例 5：<p>
 * 输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]<p>
 * 输出：[0,1,1]<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 100<p>
 * red_edges.length <= 400<p>
 * blue_edges.length <= 400<p>
 * red_edges[i].length == blue_edges[i].length == 2<p>
 * 0 <= red_edges[i][j], blue_edges[i][j] < n<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shortest-path-with-alternating-colors">1129. 颜色交替的最短路径</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1129 {

    @Test
    public void test01() {
        int n = 3;
//        int[][] redEdges = {{0, 1}, {1, 2}}, blueEdges = {};
//        int[][] redEdges = {{0, 1}}, blueEdges = {{2, 1}};
//        int[][] redEdges = {{1, 0}}, blueEdges = {{2, 1}};
//        int[][] redEdges = {{0, 1}}, blueEdges = {{1, 2}};
        int[][] redEdges = {{0, 1}, {0, 2}}, blueEdges = {{1, 0}};
        System.out.println(Arrays.toString(new Solution().shortestAlternatingPaths(n, redEdges, blueEdges)));
    }
}

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        // 从节点 0 到节点 X 的路径必须是红蓝交替的，并求出最短路径
        int[] answer = new int[n];
        // 赋初始值
        Arrays.fill(answer, -1);
        // 0 赋值为 0
        answer[0] = 0;
        List<Set<Integer>> reds = new ArrayList<>();
        List<Set<Integer>> blues = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            reds.add(new HashSet<>());
            blues.add(new HashSet<>());
        }
        // 将从节点 nums[0] 能到达的所有节点 nums[1] 全部放入 set 集合中
        for (int[] nums : redEdges) {
            reds.get(nums[0]).add(nums[1]);
        }
        for (int[] nums : blueEdges) {
            blues.get(nums[0]).add(nums[1]);
        }
        boolean redhere[] = new boolean[n];
        boolean bluehere[] = new boolean[n];
        Queue<int[]> queue = new LinkedList<>();
        // 初始设置为 -1，意为红蓝两色都可以作为初始边
        queue.add(new int[]{-1, 0, 0});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int from = cur[0], index = cur[1], step = cur[2] + 1;
            if (from == 0 || from == -1) {
                // 曾经走过红色
                Set<Integer> set = blues.get(index);
                for (Integer integer : set) {
                    if (!bluehere[integer]) {
                        bluehere[integer] = true;
                        if (answer[integer] == -1) {
                            answer[integer] = step;
                        }
                        // 下一次走红色，到达 integer
                        queue.add(new int[]{1, integer, step});
                    }
                }
            }
            if (from == 1 || from == -1) {
                // 曾经走过蓝色
                // 获取从节点 index 走蓝色路线能到达的所有节点
                Set<Integer> set = reds.get(index);
                for (Integer integer : set) {
                    // 如果可以到达的节点未曾到达过
                    if (!redhere[integer]) {
                        redhere[integer] = true;
                        // 并且该节点当前并没有路径长度
                        if (answer[integer] == -1) {
                            answer[integer] = step;
                        }
                        // 下一次走蓝色，到达 integer
                        queue.add(new int[]{0, integer, step});
                    }
                }
            }
        }
        return answer;
    }
}
